package leetcode.array_sort.movewindow;

/**
 * 209. 长度最小的子数组
 * <p>
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
 * <p>
 * 示例:
 * <p>
 * 输入: s = 7, nums = [2,3,1,2,4,3]
 * 输出: 2
 * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 * <p>
 * 进阶:
 * <p>
 * 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
 * <p>
 * 分析：使用滑动窗口：
 * 定义滑动窗口的边界 l  r  arr[l,r]  也就是说要在 l,r 区间中取寻找一个满足sum>=s的解
 * 定义 res 存放结果 初始化时候为length+1 在以后的循环中进行减
 * sum 当前arr[l,r]的和
 */
public class Solution209 {
    public static int minSubArrayLen(int s, int[] nums) {

        int l = 0, r = -1; //arr[l,r]为空，满足我们定义的边界
        int sum = 0;
        int res = nums.length + 1;//在循环中一直去最小值， 初始情况res不存在
        while (l < nums.length) {//说明还有可以滑动的窗口，即便右边r不能滑动
            if (r + 1 < nums.length && sum < s) {//r 到头，或者sum>=s
                //移动右边 sum+nums[++r]
                r++;
                sum += nums[r];
            } else {//sum >s 滑动左窗口 l  减小sum
                sum -= nums[l];
                l++;//减sum小值
            }

            //sum>= s
            if (sum >= s) {
                res = Math.min(res, r - l + 1);
            }
        }

        if (res == nums.length + 1)
            return 0;
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        System.out.println(minSubArrayLen(7, nums));
    }
}